package dataStructure.sort;
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定

/**
 * 鸡尾酒排序，也叫定向冒泡排序
 */
public class CocktailSort extends DataCrol {
    @Override
    public void sort(int[] array) {
        int left = 0;                            // 初始化边界
        int right = array.length - 1;
        while (left < right) {
            for (int i = left; i < right; i++) {   // 前半轮,将最大元素放到后面
                if (array[i] > array[i + 1]) {
                    swap(array, i, i + 1);
                }
            }
            right--;
            for (int i = right; i > left; i--) {   // 后半轮,将最小元素放到前面
                if (array[i - 1] > array[i]) {
                    swap(array, i - 1, i);
                }
            }
            left++;
        }
    }

    public static void main(String[] args) {
        CocktailSort cocktailSort = new CocktailSort();
        int[] array = DataCrol.createRandomArray(20);
        DataCrol.print(array);
        cocktailSort.sort(array);
        DataCrol.print(array);
        cocktailSort.timeTest();
    }
}
